package leetcode_zh

import (
	"container/heap"
	"math"
	"math/rand"
)

/**
 * @Description: 剑指 Offer II 001. 整数除法 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/6/18 9:12
 **/
func divide001(a int, b int) int {
	if b == 1 && a == -2147483648 {
		return -2147483648
	}
	var positive = (a > 0 && b > 0) || (a < 0 && b < 0)
	if a < 0 {
		a = -a
	}
	if b < 0 {
		b = -b
	}
	if a == 0 || b > a {
		return 0
	}
	if a < 0 {
		a = -a
	}
	if b < 0 {
		b = -b
	}
	var res = 1
	var plus = b
	for a > b {
		b += b
		res <<= 1
		if res >= math.MaxInt32 {
			res = math.MaxInt32
			b = -1
			break
		}
	}

	for b > a {
		b -= plus
		res--
	}

	if positive {
		return res
	}
	return -res
}

/**
 * @Description: 剑指 Offer 62. 圆圈中最后剩下的数字
 * @Keyword:
 * @Author: kami
 * @Date: 2022/6/27 9:16
 **/
func lastRemaining(n int, m int) int {
	var ans int
	for i := 2; i < n; i++ {
		ans = (ans + m) % i
	}
	return ans + 1
}

/**
 * @Description: 面试题 08.12. 八皇后 困难
 * @Keyword: 集合回溯法
 * @Author: kami
 * @Date: 2022/6/27 9:40
 **/
var solutions [][]string

func solveNQueens(n int) [][]string {
	solutions = [][]string{}
	queens := make([]int, n)
	for i := 0; i < n; i++ {
		queens[i] = -1
	}
	columns := map[int]bool{}
	diagonals1, diagonals2 := map[int]bool{}, map[int]bool{}
	backtrackQueen(queens, 0, columns, diagonals1, diagonals2)
	return solutions
}

func backtrackQueen(queens []int, row int, columns, diagonals1, diagonals2 map[int]bool) {
	var n = len(queens)
	if row == n {
		board := generateBoard(queens)
		solutions = append(solutions, board)
		return
	}
	for i := 0; i < n; i++ {
		if columns[i] {
			continue
		}
		// 行下标 - 列下标的差表示 左上到右下的对角线
		diagonal1 := row - i
		if diagonals1[diagonal1] {
			continue
		}
		// 行下标 + 列下标的和表示 右上到左下的对角线
		diagonal2 := row + i
		if diagonals2[diagonal2] {
			continue
		}
		queens[row] = i
		columns[i] = true
		diagonals1[diagonal1], diagonals2[diagonal2] = true, true
		backtrackQueen(queens, row+1, columns, diagonals1, diagonals2)
		queens[row] = -1
		delete(columns, i)
		delete(diagonals1, diagonal1)
		delete(diagonals2, diagonal2)
	}
}

func generateBoard(queens []int) []string {
	board := []string{}
	for i := 0; i < len(queens); i++ {
		row := make([]byte, len(queens))
		for j := 0; j < len(queens); j++ {
			row[j] = '.'
		}
		row[queens[i]] = 'Q'
		board = append(board, string(row))
	}
	return board
}

type CQueue struct {
	queue []int
}

/**
 * @Description: 剑指 Offer 09. 用两个栈实现队列 簡單
 * @Keyword:
 * @Author: kami
 * @Date: 2022/6/29 12:20
 **/
func Constructor09() CQueue {
	return CQueue{queue: make([]int, 0)}
}

func (this *CQueue) AppendTail(value int) {
	this.queue = append(this.queue, value)
}

func (this *CQueue) DeleteHead() int {
	if len(this.queue) == 0 {
		return -1
	}
	var res = this.queue[0]
	this.queue = this.queue[1:]
	return res
}

/**
 * @Description:剑指 Offer 10- I. 斐波那契数列 简单
 * @Keyword: 动态规划
 * @Author: kami
 * @Date: 2022/6/29 12:24
 **/
func fib(n int) int {
	if n == 0 {
		return 0
	}
	if n == 1 {
		return 1
	}
	var mod = 1000000007
	var dp = make([]int, n+1)
	dp[0] = 0
	dp[1] = 1
	for i := 2; i <= n; i++ {
		dp[i] = (dp[i-1] + dp[i-2]) % mod
	}
	return dp[n]
}

/**
 * @Description: 剑指 Offer 03. 数组中重复的数字
 * @Keyword:
 * @Author: kami
 * @Date: 2022/6/29 12:28
 **/
func findRepeatNumber(nums []int) int {
	var repeat = make([]int, len(nums))
	repeat[0] = -1
	for i := 0; i < len(nums); i++ {
		if repeat[nums[i]] == nums[i] {
			return nums[i]
		}
		repeat[nums[i]] = nums[i]
	}
	return 0
}

/**
 * @Description: 剑指 Offer 10- II. 青蛙跳台阶问题 简单
 * @Keyword: 动态规划
 * @Author: kami
 * @Date: 2022/6/29 14:59
 **/
func numWays(n int) int {
	if n < 2 {
		return 1
	}

	var dp = make([]int, n)
	dp[0] = 1
	dp[1] = 2
	var mod = 1000000007
	for i := 2; i < n; i++ {
		dp[i] = (dp[i-1] + dp[i-2]) % mod
	}
	return dp[n-1]
}

/**
 * @Description: 剑指 Offer 11. 旋转数组的最小数字 简单
 * @Keyword: 移动一次的升序数组中找到最小的数字
 * @Author: kami
 * @Date: 2022/6/29 20:27
 **/
func minArray(numbers []int) int {
	if len(numbers) == 1 {
		return numbers[0]
	}
	var left = 0
	var right = len(numbers) - 1
	for left < right {
		var mid = (left + right) / 2
		// 只要右侧大于中间，右侧就是升序的
		if numbers[right] > numbers[mid] {
			right = mid
		} else if numbers[right] < numbers[mid] {
			left = mid + 1
		} else {
			right--
		}
	}
	return numbers[left]
}

/**
 * @Description: 剑指 Offer 05. 替换空格 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/6/29 21:01
 **/
func replaceSpace(s string) string {
	var res []byte
	for i := 0; i < len(s); i++ {
		if s[i] == ' ' {
			res = append(res, '%', '2', '0')
		} else {
			res = append(res, s[i])
		}
	}
	return string(res)
}

func reversePrint(head *ListNode) []int {
	var curNode = head
	var res []int
	for curNode != nil {
		res = append([]int{curNode.Val}, res...)
		curNode = curNode.Next
	}
	return res
}

/**
 * @Description: 剑指 Offer 25. 合并两个排序的链表 简单
 * @Keyword: TODO
 * @Author: kami
 * @Date: 2022/6/29 21:08
 **/
func mergeTwoLists25(l1 *ListNode, l2 *ListNode) *ListNode {
	var dumyHead = &ListNode{}
	var curNode = dumyHead
	for l1 != nil || l2 != nil {
		if l1 != nil && l2 != nil {
			if l1.Val < l2.Val {
				curNode.Next = l1
				l1 = l1.Next
			} else {
				curNode.Next = l2
				l2 = l2.Next
			}
			curNode = curNode.Next
		} else if l1 != nil {
			curNode.Next = l1
			return dumyHead.Next
		} else {
			curNode.Next = l2
			return dumyHead.Next
		}
	}
	return dumyHead.Next
}

/**
 * @Description: 剑指 Offer 27. 二叉树的镜像 简单
 * @Keyword: 递归
 * @Author: kami
 * @Date: 2022/6/29 21:19
 **/
func mirrorTree(root *TreeNode) *TreeNode {
	if root == nil {
		return root
	}
	if root.Left != nil || root.Right != nil {
		root.Left, root.Right = root.Right, root.Left
		mirrorTree(root.Left)
		mirrorTree(root.Right)
	}
	return root
}

/**
 * @Description: 剑指 Offer 28. 对称的二叉树 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/6/29 21:27
 **/
func isSymmetric28(root *TreeNode) bool {
	if root == nil || (root.Left == nil && root.Right == nil) {
		return true
	}
	var dfs func(left, right *TreeNode) bool
	dfs = func(left, right *TreeNode) bool {
		if left != nil && right != nil {
			if left.Val != right.Val {
				return false
			}
			return dfs(left.Left, right.Right) && dfs(left.Right, right.Left)
		}
		if left == nil && right == nil {
			return true
		}
		return false
	}
	return dfs(root.Left, root.Right)
}

/**
 * @Description: 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 简单
 * @Keyword: 快排思想
 * @Author: kami
 * @Date: 2022/6/29 21:39
 **/
func exchange(nums []int) []int {
	var left = 0
	var right = len(nums) - 1
	for left < right {
		for left < right && nums[left]%2 == 1 {
			left++
		}
		for left < right && nums[right]%2 == 0 {
			right--
		}
		nums[left], nums[right] = nums[right], nums[left]
	}
	return nums
}

/**
 * @Description: 剑指 Offer 15. 二进制中1的个数 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/6/29 21:42
 **/
func hammingWeight(num uint32) int {
	var cnt int
	for num > 0 {
		if num&1 > 0 {
			cnt++
		}
		num >>= 1
	}
	return cnt
}

/**
 * @Description: 剑指 Offer 29. 顺时针打印矩阵 简单
 * @Keyword: 模拟
 * @Author: kami
 * @Date: 2022/6/29 21:50
 **/
func spiralOrder(matrix [][]int) []int {
	if len(matrix) == 0 {
		return nil
	}
	step := 0
	size := len(matrix) * len(matrix[0])
	//定义四个方向的端点
	top, bottom, right, left := 0, len(matrix)-1, len(matrix[0])-1, 0
	nums := make([]int, size)
	for step < size {
		//从左到右
		for i := left; i <= right && step < size; i++ {
			nums[step] = matrix[top][i]
			step++
		}
		top++
		//从上到下
		for i := top; i <= bottom && step < size; i++ {
			nums[step] = matrix[i][right]
			step++
		}
		right--
		//从右到左
		for i := right; i >= left && step < size; i-- {
			nums[step] = matrix[bottom][i]
			step++
		}
		bottom--
		//从下到上
		for i := bottom; i >= top && step < size; i-- {
			nums[step] = matrix[i][left]
			step++
		}
		left++
	}
	return nums
}

/**
 * @Description: 剑指 Offer 22. 链表中倒数第k个节点 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/6/30 8:33
 **/
func getKthFromEnd(head *ListNode, k int) *ListNode {
	var quick = head
	var slow = head
	var step = 0
	for quick != nil {
		if step < k {
			quick = quick.Next
			step++
		} else {
			slow = slow.Next
			quick = quick.Next
		}
	}
	return slow
}

/**
 * @Description: 剑指 Offer 17. 打印从1到最大的n位数 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/6/30 8:37
 **/
func printNumbers(n int) []int {
	var max int
	for n > 0 {
		max = max*10 + 9
		n--
	}
	var res []int
	for i := 1; i <= max; i++ {
		res = append(res, i)
	}
	return res
}

/**
 * @Description: 剑指 Offer 24. 反转链表 简单
 * @Keyword: TODO
 * @Author: kami
 * @Date: 2022/6/30 8:40
 **/
func reverseList24(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	var curNode = head
	var pre *ListNode
	var next = head.Next

	for next != nil {
		var newNext = next.Next
		curNode.Next = pre
		next.Next = curNode

		pre = curNode
		curNode = next
		next = newNext
	}
	return curNode
}

/**
 * @Description: 剑指 Offer 18. 删除链表的节点 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/6/30 8:55
 **/
func deleteNode(head *ListNode, val int) *ListNode {
	if head.Val == val {
		return head.Next
	}
	var pre *ListNode
	var cur = head
	for cur != nil {
		if cur.Val != val {
			pre = cur
			cur = cur.Next
		} else {
			pre.Next = cur.Next
			cur.Next = nil
			return head
		}
	}
	return head
}

/**
 * @Description: 面试题40. 最小的k个数 简单
 * @Keyword: 快排思想
 * @Author: kami
 * @Date: 2022/6/30 9:00
 **/
func getLeastNumbers(arr []int, k int) []int {
	var res []int
	n := len(arr)
	if n == 0 || k <= 0 || n < k {
		return res
	}
	pq := &maxHeap{}
	for i := 0; i < k; i++ {
		heap.Push(pq, arr[i])
	}
	// heapify
	heap.Init(pq)
	for i := k; i < n; i++ {
		if pq.Len() > 0 && arr[i] < pq.Peek().(int) {
			heap.Pop(pq)
			heap.Push(pq, arr[i])
		}
	}

	for i := 0; i < k; i++ {
		res = append(res, heap.Pop(pq).(int))
	}
	return res
}

// 基于go interface实现最大堆
type maxHeap []int

func (h *maxHeap) Len() int {
	return len(*h)
}

func (h *maxHeap) Less(i, j int) bool {
	return (*h)[i] > (*h)[j]
}

func (h *maxHeap) Swap(i, j int) {
	(*h)[i], (*h)[j] = (*h)[j], (*h)[i]
}

func (h *maxHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *maxHeap) Pop() (v interface{}) {
	*h, v = (*h)[:h.Len()-1], (*h)[h.Len()-1]
	return
}

// 查看堆顶元素
func (h *maxHeap) Peek() interface{} {
	return (*h)[0]
}

var kk int

func getLeastNumbers40(arr []int, k int) []int {
	kk = k
	quickSort(arr, 0, len(arr)-1)
	return arr[:k]
}
func quickSort(nums []int, left, right int) bool {
	if left > right {
		return false
	}
	key := rand.Int()%(right-left+1) + left
	nums[left], nums[key] = nums[key], nums[left]
	i, j, pivot := left, right, nums[left]
	for i < j {
		for i < j && nums[j] >= pivot { //如果是求前k大,这里nums[j]>=pivot改成 nums[j]<=pivot
			j--
		}
		for i < j && nums[i] <= pivot { //如果是求前k大,这里nums[i]<=pivot改成 nums[i]>=pivot即可
			i++
		}
		nums[i], nums[j] = nums[j], nums[i]
	}
	nums[left], nums[i] = nums[i], nums[left]
	if kk <= left { //left之前的元素都已经有序了,那么当kk<=left时直接return即可
		return true
	}
	if quickSort(nums, left, i-1) {
		return true
	}
	if quickSort(nums, i+1, right) {
		return true
	}
	return false
}

/**
 * @Description: 剑指 Offer 04. 二维数组中的查找 中等
 * @Keyword: 站在右上角看。这个矩阵其实就像是一个Binary Search Tree
 * @Author: kami
 * @Date: 2022/6/30 10:47
 **/
func findNumberIn2DArray(matrix [][]int, target int) bool {
	// 右上角
	if len(matrix) == 0 {
		return false
	}
	var m = 0
	var n = len(matrix[0]) - 1
	for m < len(matrix) && n >= 0 {
		if matrix[m][n] > target {
			n--
		} else if matrix[m][n] < target {
			m++
		} else {
			return true
		}
	}
	return false

	// 左下角
	//var i = len(matrix) - 1
	//var j = 0
	//for i > 0 && j < len(matrix[0]) {
	//	if matrix[i][j] > target {
	//		i--
	//	} else if matrix[i][j] < target {
	//		j++
	//	} else {
	//		return true
	//	}
	//}
	//return false
}

/**
 * @Description:  剑指 Offer 30. 包含min函数的栈 简单
 * @Keyword:  链表，每个节点加一个额外属性：当前最小值
 * @Author: kami
 * @Date: 2022/6/30 12:04
 **/
type MinStack30 struct {
	topNde *StackNode
}
type StackNode struct {
	val    int
	next   *StackNode
	curMin *StackNode
}

/** initialize your data structure here. */
func Constructor30() MinStack30 {
	return MinStack30{}
}

func (this *MinStack30) Push30(x int) {
	xNode := &StackNode{
		val:  x,
		next: this.topNde,
	}
	xNode.curMin = xNode

	if this.topNde != nil {
		if x > this.topNde.curMin.val {
			xNode.curMin = this.topNde.curMin
		}
		xNode.next = this.topNde
		this.topNde = xNode
		return
	}

	this.topNde = xNode
}

func (this *MinStack30) Pop30() {
	if this.topNde != nil {
		this.topNde = this.topNde.next
	}
}

func (this *MinStack30) Top30() int {
	if this.topNde != nil {
		return this.topNde.val
	}
	return -1
}

func (this *MinStack30) Min30() int {
	if this.topNde != nil {
		return this.topNde.curMin.val
	}
	return -1
}

/**
 * @Description: 剑指 Offer 42. 连续子数组的最大和
 * @Keyword:
 * @Author: kami
 * @Date: 2022/6/30 16:58
 **/
func maxSubArray42(nums []int) int {
	var max = math.MinInt32
	var curSum int
	for i := 0; i < len(nums); i++ {
		curSum += nums[i]
		if curSum > max {
			max = curSum
		}
		if curSum < 0 {
			curSum = 0
		}
	}
	return max
}

/**
 * @Description: 剑指 Offer 39. 数组中出现次数超过一半的数字 简单
 * @Keyword: 极限一换一
 * @Author: kami
 * @Date: 2022/6/30 17:02
 **/
func majorityElement(nums []int) int {
	var res int
	var cnt int
	for i := 0; i < len(nums); i++ {
		if cnt == 0 {
			res = nums[i]
			cnt++
		} else {
			if res == nums[i] {
				cnt++
			} else {
				cnt--
			}
		}
	}
	return res
}

/**
 * @Description: 剑指 Offer 32 - II. 从上到下打印二叉树 II 简单
 * @Keyword: 层序遍历
 * @Author: kami
 * @Date: 2022/6/30 17:24
 **/
func levelOrder32(root *TreeNode) [][]int {
	if root == nil {
		return [][]int{}
	}
	var res [][]int
	var stack = []*TreeNode{root}
	for len(stack) > 0 {
		var nextStack []*TreeNode
		var curRes []int
		for i := 0; i < len(stack); i++ {
			curRes = append(curRes, stack[i].Val)
			if stack[i].Left != nil {
				nextStack = append(nextStack, stack[i].Left)
			}
			if stack[i].Right != nil {
				nextStack = append(nextStack, stack[i].Right)
			}
		}
		res = append(res, curRes)
		stack = nextStack
	}
	return res
}

/**
 * @Description: 剑指 Offer 50. 第一个只出现一次的字符 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/6/30 17:28
 **/
func firstUniqChar(s string) byte {
	// 次数
	var seen = make([]int, 26)
	for i := 0; i < len(s); i++ {
		var char = s[i] - 'a'
		if seen[char] > 0 {
			seen[char] = -1
		} else if seen[char] == 0 {
			seen[char] = 1
		}
	}
	for i := 0; i < len(s); i++ {
		if seen[s[i]-'a'] == 1 {
			return s[i]
		}
	}
	return ' '
}

/**
 * @Description: 剑指 Offer 55 - I. 二叉树的深度 简单
 * @Keyword: 递归
 * @Author: kami
 * @Date: 2022/6/30 17:38
 **/
func maxDepth55(root *TreeNode) int {
	if root != nil {
		var left = 1 + maxDepth55(root.Left)
		var right = 1 + maxDepth55(root.Right)
		if left < right {
			return right
		}
		return left
	}
	return 0
}

/**
 * @Description: 剑指 Offer 57. 和为s的两个数字 简单
 * @Keyword: 有序数组
 * @Author: kami
 * @Date: 2022/6/30 17:41
 **/
func twoSum57(nums []int, target int) []int {
	var need = make(map[int]int)
	for i := 0; i < len(nums); i++ {
		if idx, ok := need[nums[i]]; ok {
			return []int{nums[idx], nums[i]}
		}
		need[target-nums[i]] = i
	}
	return []int{}
}
func twoSumDoublePointer(nums []int, target int) []int {
	var left = 0
	var right = len(nums) - 1
	for left < right {
		var sum = nums[left] + nums[right]
		if sum == target {
			return []int{nums[left], nums[right]}
		} else if sum > target {
			right--
		} else {
			left++
		}
	}
	return []int{}
}

/**
 * @Description: 剑指 Offer 57 - II. 和为s的连续正数序列 简单
 * @Keyword: 滑动窗口
 * @Author: kami
 * @Date: 2022/6/30 17:48
 **/
func findContinuousSequence(target int) [][]int {
	var res [][]int
	var left = 1
	var right = 1
	var sum = 0
	var half = target / 2
	for left <= half {
		if sum < target {
			sum += right
			right++
		} else if sum > target {
			sum -= left
			left++
		} else {
			var curRes []int
			for i := left; i < right; i++ {
				curRes = append(curRes, i)
			}
			res = append(res, curRes)
			sum -= left
			left++
		}
	}
	return res

}

/**
 * @Description: 剑指 Offer 52. 两个链表的第一个公共节点
 * @Keyword: 双指针调动
 * @Author: kami
 * @Date: 2022/6/30 18:20
 **/
func getIntersectionNode(headA, headB *ListNode) *ListNode {
	if headA == nil || headB == nil {
		return nil
	}
	var curA = headA
	var curB = headB
	var turnTime int
	for curA != curB && turnTime <= 2 {
		if curA.Next == nil {
			curA = headB
			turnTime++
		} else {
			curA = curA.Next
		}
		if curB.Next == nil {
			curB = headA
			turnTime++
		} else {
			curB = curB.Next
		}
	}
	if turnTime > 2 {
		return nil
	}
	return curA
}

/**
 * @Description: 剑指 Offer 58 - I. 翻转单词顺序 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/6/30 18:35
 **/
func reverseWords(s string) string {
	if len(s) == 0 {
		return s
	}
	var res string
	var curStr []byte
	var start int
	for i := 0; i < len(s); i++ {
		if s[i] != ' ' {
			start = i
			break
		}
	}
	var end int
	for i := len(s) - 1; i >= 0; i-- {
		if s[i] != ' ' {
			end = i
			break
		}
	}
	if start == end && s[start] == ' ' {
		return ""
	}
	for i := end; i >= start; i-- {
		if s[i] != ' ' {
			curStr = append([]byte{s[i]}, curStr...)
			if i == start {
				res += string(curStr)
			}
		} else if s[i] == ' ' && s[i+1] != ' ' {
			res += string(curStr) + " "
			curStr = []byte{}
		}
	}
	return res
}

/**
 * @Description: 剑指 Offer 53 - I. 在排序数组中查找数字 I
 * @Keyword: 二分查找
 * @Author: kami
 * @Date: 2022/6/30 19:50
 **/
func search53(nums []int, target int) int {
	return helper53(nums, target) - helper53(nums, target-1)
}

func helper53(nums []int, target int) int {
	var i = 0
	var j = len(nums) - 1
	for i <= j {
		var m = (i + j) / 2
		if nums[m] <= target {
			i = m + 1
		} else {
			j = m - 1
		}
	}
	return i
}

/**
 * @Description: 剑指 Offer 58 - II. 左旋转字符串 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/6/30 20:22
 **/
func reverseLeftWords(s string, n int) string {
	var res = make([]byte, len(s))
	for i := 0; i < len(s); i++ {
		if i < n {
			res[len(s)-n+i] = s[i]
		} else {
			res[i-n] = s[i]
		}
	}
	return string(res)
}

/**
 * @Description: 剑指 Offer 53 - II. 0～n-1中缺失的数字 简单
 * @Keyword: TODO
 * @Author: kami
 * @Date: 2022/6/30 20:26
 **/
func missingNumber(nums []int) int {
	for i := 0; i < len(nums); i++ {
		if i != nums[i] {
			return i
		}
	}
	return len(nums)
}

/**
 * @Description: 剑指 Offer 54. 二叉搜索树的第k大节点 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/6/30 20:33
 **/
func kthLargest(root *TreeNode, k int) int {
	var dfs func(node *TreeNode)
	var res int
	dfs = func(node *TreeNode) {
		if root == nil {
			return
		}
		dfs(root.Right)
		if k == 0 {
			return
		}
		k--
		if k == 0 {
			res = root.Val
		}

		dfs(root.Left)
	}
	dfs(root)
	return res
}

/**
 * @Description: 剑指 Offer 65. 不用加减乘除做加法 简单
 * @Keyword: 位运算；无进位和 与 异或运算 规律相同，进位 和 与运算 规律相同
 * @Author: kami
 * @Date: 2022/7/1 9:15
 **/
func add(a int, b int) int {
	if b == 0 {
		return a
	}
	return add(a^b, (a&b)<<1)
}

/**
 * @Description: 剑指 Offer 61. 扑克牌中的顺子  简单
 * @Keyword: TODO
 * @Author: kami
 * @Date: 2022/7/1 10:06
 **/
func isStraight(nums []int) bool {
	var s int
	vis := make([]int, 14)
	min, max := 14, -1
	for _, v := range nums {
		vis[v]++
		if v == 0 {
			s++
			continue
		}
		if vis[v] > 1 {
			return false
		}

		if v > max {
			max = v
		}

		if v < min {
			min = v
		}
	}

	if max-min == 4 {
		return true
	} // 没有大王和小王的情况
	return max-min-s <= 1 // 有大小王的场景，判断能否替换缺少的牌，以构成顺子
}

/**
 * @Description: 剑指 Offer 55 - II. 平衡二叉树
 * @Keyword: 递归
 * @Author: kami
 * @Date: 2022/7/1 11:24
 **/
func isBalanced(root *TreeNode) bool {
	var dfs func(node *TreeNode) (int, bool)
	dfs = func(node *TreeNode) (int, bool) {
		if node == nil {
			return 0, true
		}
		left, lBal := dfs(node.Left)
		right, rBal := dfs(node.Right)
		if !lBal || !rBal {
			return 0, false
		}
		if left-right > 1 || left-right < -1 {
			return 0, false
		}
		if left > right {
			return 1 + left, true
		}
		return 1 + right, true
	}
	_, ok := dfs(root)
	return ok
}

/**
 * @Description: 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先 简单
 * @Keyword: 2种方法 1.两次遍历，拿到两个节点的路径，路径中最后一个相同的节点是结果 2.一次遍历，同时判断
 * @Author: kami
 * @Date: 2022/7/1 12:15
 **/
func lowestCommonAncestor68(root, p, q *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	if root.Val > p.Val && root.Val > q.Val {
		return lowestCommonAncestor68(root.Left, q, p)
	}
	if root.Val < p.Val && root.Val < q.Val {
		return lowestCommonAncestor68(root.Right, q, p)
	}
	return root
}

/**
 * @Description: 剑指 Offer 68 - II. 二叉树的最近公共祖先 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/1 12:15
 **/
func lowestCommonAncestor682(root, p, q *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	if root.Val == p.Val || root.Val == q.Val {
		return root
	}
	left := lowestCommonAncestor(root.Left, p, q)
	right := lowestCommonAncestor(root.Right, p, q)
	if left != nil && right != nil {
		return root
	}
	if left == nil {
		return right
	}
	return left
}

/**
 * @Description: 剑指 Offer 12. 矩阵中的路径 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/1 12:47
 **/
func exist12(board [][]byte, word string) bool {
	var visited = make([][]byte, len(board))
	for i := 0; i < len(board); i++ {
		visited[i] = make([]byte, len(board[0]))
	}
	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board[0]); j++ {
			if findTarget(board, visited, word, i, j, 0) {
				return true
			}
		}
	}
	return false
}

func findTarget(board, visited [][]byte, word string, m, n, idx int) bool {
	var idxIllegal = m < 0 || m == len(board) || n < 0 || n == len(board[0]) || idx == len(word)
	if idxIllegal || visited[m][n] == 1 || word[idx] != board[m][n] {
		return false
	}
	if idx == len(word)-1 && word[idx] == board[m][n] {
		return true
	}
	visited[m][n]++
	// 向上
	var ans = findTarget(board, visited, word, m-1, n, idx+1) ||
		findTarget(board, visited, word, m+1, n, idx+1) ||
		findTarget(board, visited, word, m, n-1, idx+1) ||
		findTarget(board, visited, word, m, n+1, idx+1)
	visited[m][n]--
	return ans
}

/**
 * @Description: 剑指 Offer 13. 机器人的运动范围 中等
 * @Keyword: 回溯
 * @Author: kami
 * @Date: 2022/7/1 13:40
 **/
func movingCount(m int, n int, k int) int {
	var visited = make([][]bool, m)
	for i := 0; i < m; i++ {
		visited[i] = make([]bool, n)
	}
	var dfs func(i, j, m, n, k int, visited [][]bool) int
	dfs = func(i, j, m, n, k int, visited [][]bool) int {
		if i < 0 || i == m || j < 0 || j == n || (i/10+i%10+j/10+j%10) > k || visited[i][j] {
			return 0
		}
		visited[i][j] = true
		return dfs(i+1, j, m, n, k, visited) +
			dfs(i-1, j, m, n, k, visited) +
			dfs(i, j+1, m, n, k, visited) +
			dfs(i, j-1, m, n, k, visited) + 1
	}

	return dfs(0, 0, m, n, k, visited)
}
